In many wireless communication networks, devices are not synchronized to a single reference clock. Instead, each device relies on its own clock. Due to the limitation of the hardware, manufacturing processes, temperature drift, component aging, etc., the actual operating frequency of the clock is generally different from the designed nominal frequency. For example, if a 100 MHz clock signal is generated by a crystal that has a tolerance of +/−20 parts per million (ppm), the actual frequency of the clock can be any value in a range from 99,998,000 Hz to 100,002,000 Hz.
A difference between the actual frequency of the clock and the designed nominal frequency is referred to as the ‘clock frequency offset’ (CFO) or ‘absolute clock frequency offset’ (ACFO). The difference between the frequencies of two independent clocks (with the same nominal frequency) is called ‘relative clock frequency offset’ (RCFO). For example, for two clocks with nominal frequency of 100 MHz, if one clock has a frequency of 99,998,000 Hz and the other clock has a frequency of 100,002,000 Hz. The RCFO is 4 KHz, or 40 ppm.
The CFO and RCFO can cause problem. When the clock is used for time measurement, the ACFO and/or RCFO introduce errors. In digital circuit, time is generally measured as the number of clock cycles between two time instances
      N    =                  t                  T          actual                    =              t        ·                  f          actual                      ,where Tactual is the actual clock period, and factual is the actual clock frequency. As an example, a timer based on an accurate 100 MHz clock will count 100,000 clock cycles in a 1 millisecond period. If the ACFO is −20 ppm, the actual count is ˜99,998 clock cycles instead. If the ACFO is not compensated, which is often the case when the device has not knowledge of the ACFO of its own clock, then the time is simply computed using the nominal frequency:
                                                                           t                =                                ⁢                                  N                  ·                                      T                    norm                                                                                                                          =                                ⁢                                  N                                      f                    norm                                                                                                                          =                                ⁢                                  t                  ·                                                            f                      actual                                                              f                      norm                                                                                                                                              =                                ⁢                                  t                  +                                      t                    ·                                                                  Δ                        ⁢                                                                                                  ⁢                                                  f                          abs                                                                                            f                        norm                                                                                                                                                      (          1          )                    where Tnorm is the nominal clock period, fnorm is the nominal clock frequency, and Δfabs is the ACFO. In the example, fnorm=100 MHz, t=999,980 ns, which results in a 20 ns time error.
If the same time period is measured by two devices using independent clocks, the RCFO causes a discrepancy in the measurements. For example, if the nominal clock frequency is 100 MHz for both timer X and timer Y, timer X has a −20 ppm offset and timer Y has a +20 ppm offset, which is a RCFO of 40 ppm. A 1 msec time period will be measured as 99,998,000 ns and 100,002,000 ns respectively for timer X and timer Y, a difference of 40 ns.
The RCFO has a significant impact on the ranging accuracy of a two-way TOA (TW-TOA) system. A TW-TOA is a method can also be used for ranging between two transceivers. TW-TOA does not require exact synchronization between the transmitter and receiver. The TW-TOA ranging method is used in the IEEE 802.15.4a standard.
In TW-TOA, two transceivers exchange packets and the round trip delay is measured. A typical exchange is as follows: the first device transmits a packet to the second device. After receiving the packet, the second device transmits a packet back to the first device. The first device measures the total time elapsed from the transmission of the first packet to the reception of the second packet. The second device measures the time elapsed from the reception of the first packet to the transmission of the second packet. The round trip travel time of the signal is calculated as the difference between these two measured values. The distance between the devices is calculated as the product of one half of the round trip traveling time multiplied by the speed of the signal (3×108 meter/sec in free space for electromagnetic signal).
Because the turnaround time at the second device is much larger than the signal ‘flying’ time, the error caused by RCFO is the dominant factor in the overall time estimation error for a TW-TOA system. If the devices can obtain an accurate estimation of the RCFO, then the time estimation accuracy can be improved by compensating for it. Clearly, an accurate RCFO estimation is very important in achieving accurate time measurement.
FIG. 4 shows a prior art ranging procedure. Device X transmits a request packet (ranging-req) 111 at time t0. The packet is received by device Y at time t1. After some delay, device Y transmits an acknowledge packet (ranging-ack) 112 at time t2. The range-ack packet is received by device X at time t3. The turn-around delay t12 is measured by device Y and sent to device X either in the ranging-ack packet, or in a separate packet (ranging-data). The delay t03 is measured by device X.
Let tp be the ‘fly’ time of the signal. Without considering the frequency offsets, the estimated round-trip fly time is2·t′p=tX03−tY12,and tX03 the measured round-trip time from the transmission of the range-request packet to the reception of the range-acknowledge packet by device X based on its clock clkX, and tY12 is the measured turn-around time from the beginning of the received ranging-request packet to the beginning of the transmitted ranging-acknowledge packet by device Y based on its clock clkY.
The range between device X and Y isDXY=t′p·C, where C is the speed of the electromagnetic signals, e.g., 3×108 m/sec in free space.
Because the true round-trip fly time is2·tp=t03−t12,tX03=NX03/f=t03·fX/f, andtY12=nY12/f=t12·fY/f, andthe estimation error isΔtp=t′p−tp=(tX03−tY12)−(t03−t12).
Given that the process time is much longer than the fly time and t12>>2tp,Δtp=(tX03−t03)−(tY12−t12)=t12(ΔfXY/f)+2tp(ΔfX/f≈t12(ΔfXY/f),where ΔfX is the frequency offset of the timer clock with respect to the nominal frequency f and ΔfXY is the relative frequency offset between the timer clock for device X and the timer clock for device Y. The above equation indicates that reducing t12 and ΔfXY/f will improve the time estimation accuracy. However, in practice, the desired improvements may not be feasible. ΔfXY/f is determined by the components performance (in particular, the crystal oscillator) and a higher accuracy/stability components are more costly and may require more complicated circuit design.
The process time, t12 is often determined by several factors and cannot be easily reduced because many communication standards impose a quite period between transmissions, and the receiving device must process the data and pass the packet to the upper layer and the processing time is long, and the length of the payload portion of the packet is often non-zero.
Conventional methods for estimating the RCFO in wireless systems include the following.
One method uses the preamble of a received packet. Generally the preamble of the packet includes multiple symbols. By measuring a length of the preamble or a time interval between two symbols, the receiving device can estimate the RCFO of its clock with respect to the clock of the transmitting device. Such a method does not yield an accurate RCFO estimation because the preamble has a finite duration. Therefore, the time interval between two symbols cannot be very large, the method does not benefit from the processing gain by using as many symbols in the preamble, and the method is sensitive to carrier frequency offset and sample timing errors.
A symmetric double-sided two-way protocol exchange data/ranging packet between two devices in the following sequence:                Device A transmits a first packet;        Device B receives the first packet;        Device B transmits a second packet;        Device A receives the second packet;        Device A transmits a third packet; and        Device B receives the third packet.        Devices A and B exchange the timing information in additional data packets.        
Device A measures a round trip time troundA between transmitting the first packet and receiving the second packet. Device B measures a reply time treplyB between receiving the first packet and transmitting the second packet, and device A measures a reply time treplyA between receiving the second packet and transmitting the third packet.
The drawbacks of such a method are: the times treplyA and treplyB must be identical or very close in order to cancel out the error caused by the RCFO; additional transmissions are needed to pass the information from one device to the other device; and delay mismatches in RF frond ends of two devices may introduce additional errors.
Another method uses a combination of preamble and payload section or possibly post amble, see U.S. patent application Ser. No. 11/749,517, “Method for Reducing Radio Ranging Errors Due to Clock Frequency Offsets,” filed by Sahinoglu on Jun. 30, 2007, incorporated here in by reference.
Another method uses frequency domain analysis. By performing a fast Fourier transform (FFT) on part or all of the preamble of a packet, the RCFO can be estimated. This approach requires the storage of a large number of samples, a complex FFT operation and therefore requires additional hardware, software and power. The accuracy is dependent on the signal-to-noise ratio (SNR) of the received signal and the size of the preamble portion used for FFT.
It is desired to provide a method for estimating the RCFO without the above problems and complexities.